package braden.cis.uab.edu.automaton;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import android.content.Context;

public class Automaton {

	private Context context;
	private ArrayList<State> states;
	private ArrayList<Transition> transitions;

	public Automaton(Context context, ArrayList<State> states,
			ArrayList<Transition> transitions) {

		this.context = context;
		this.states = states;
		this.transitions = transitions;

	}

	public Automaton(Context context) {
		this.context = context;
		states = new ArrayList<State>();
		transitions = new ArrayList<Transition>();
	}

	// needs to be deterministic to use
	public Automaton getComplement() {
		if (this.isDeterministic()) {
			for (State state : states) {
				state.setFinal(!state.isFinal());
			}
			return this;
		} else {
			Automaton comp = this.convertToDFA();
			for (State state : comp.getStates()) {
				state.setFinal(!state.isFinal());
			}
			return comp;
		}
	}

	public Automaton getReverse() {

		ArrayList<Transition> changedTransitions = new ArrayList<Transition>();
		State newStartState = new State(context, 0);

		for (State state : states) {
			for (Transition transition : state.getTransitions()) {
				if (changedTransitions.contains(transition)) {
					transitions.remove(transition);
					state.removeTransition(transition);
					transition.setStartState(transition.getEndState());
					transition.setEndState(state);
					state.addTransition(transition);
					transitions.add(transition);
					changedTransitions.add(transition);
				}
			}

			if (state.isInitial()) {
				if (state.isFinal()) {
					newStartState.setFinal(true);
				}
			}

			if (state.isFinal()) {
				Transition newTransition = new Transition(newStartState, state);
				transitions.add(newTransition);
				newStartState.addTransition(newTransition);
				state.setFinal(false);
			}
		}

		for (State state : states) {
			if (state.isInitial()) {
				state.setInitial(false);
				newStartState.setInitial(true);
				state.setFinal(true);
				break;
			}
		}

		states.add(newStartState);

		return this;
	}

	public Automaton getUnion(Automaton secondAutomaton) {

		State newStartState = new State(context, states.size());
		newStartState.setInitial(true);
		states.addAll(secondAutomaton.states);
		transitions.addAll(secondAutomaton.transitions);
		for (State state : states) {
			if (state.isInitial()) {
				Transition newTransition = new Transition(newStartState, state);
				newStartState.addTransition(newTransition);
				transitions.add(newTransition);
				state.setInitial(false);
			}
		}
		states.add(newStartState);
		return this;
	}

	// if a transition from a final state to the start state already exists we
	// should add epsilon to that rather than create a new transition
	public Automaton getKleeneStar() {

		State startState = null;

		for (State state : states) {
			if (state.isInitial()) {
				startState = state;
				startState.setInitial(false);
				break;
			}
		}

		for (State state : states) {
			if (state.isFinal()) {
				Transition newTransition = new Transition(state, startState);
				state.addTransition(newTransition);
				transitions.add(newTransition);
			}
		}

		State newStartState = new State(context, states.size());
		newStartState.setInitial(true);
		newStartState.setFinal(true);
		states.add(newStartState);

		Transition newTransition = new Transition(newStartState, startState);
		newStartState.addTransition(newTransition);
		transitions.add(newTransition);

		return this;
	}

	public Automaton getConcatenation(Automaton secondAutomaton) {

		for (State state : states) {
			if (state.isFinal()) {
				Transition newTransition = new Transition(state,
						secondAutomaton.getStartState());
				state.addTransition(newTransition);
				transitions.add(newTransition);
				state.setFinal(false);
			}
		}
		secondAutomaton.getStartState().setInitial(false);
		states.addAll(secondAutomaton.states);
		transitions.addAll(secondAutomaton.transitions);
		return this;

	}

	public boolean testString(char[] characters) {

		HashSet<State> currentStates = new HashSet<State>();
		currentStates.add(getStartState());
		currentStates.addAll(getNextStatesAfterEpsilonJump(getStartState()));

		for (int i = 0; i < characters.length; i++) {
			HashSet<State> found = new HashSet<State>();
			for (Iterator<State> iterator = currentStates.iterator(); iterator
					.hasNext();) {
				State currentState = iterator.next();
				found.addAll(getNextStates(currentState, characters[i]));
				iterator.remove();
			}
			currentStates.addAll(found);
			for (State foundState : found) {
				currentStates.addAll(getNextStatesAfterEpsilonJump(foundState));
			}
			found.removeAll(found);
		}

		for (State state : currentStates) {
			if (state.isFinal()) {
				return true;
			}
		}
		return false;
	}

	public HashSet<State> getNextStates(State currentState, char character) {

		HashSet<State> newStates = new HashSet<State>();
		for (Transition transition : currentState.getTransitions()) {
			if (transition.getLabels().contains(character)) {
				newStates.add(transition.getEndState());
			}
		}
		return newStates;
	}

	public HashSet<State> getNextStatesAfterEpsilonJump(State currentState) {

		HashSet<State> newStates = new HashSet<State>();
		HashSet<State> found = new HashSet<State>();
		boolean change = true;

		found.addAll(getNextStates(currentState, 'ɛ'));
		change = !newStates.containsAll(found);
		newStates.addAll(found);
		found.removeAll(found);

		while (change) {
			for (State state : newStates) {
				found.addAll(getNextStates(state, 'ɛ'));
			}
			change = !newStates.containsAll(found);
			newStates.addAll(found);
			found.removeAll(found);
		}
		;

		return newStates;
	}

	public ArrayList<State> getStates() {
		return states;
	}

	public ArrayList<Transition> getTransitions() {
		return transitions;
	}

	public State getStartState() {
		for (State state : states) {
			if (state.isInitial()) {
				return state;
			}
		}
		return null;
	}

	public int getNumberOfStates() {
		return states.size();
	}

	public int getNumberOfTransitions() {
		return transitions.size();
	}

	public boolean isDeterministic() {
		ArrayList<Character> alphabet = new ArrayList<Character>();
		HashSet<Character> alphabetWithoutDuplicates = new HashSet<Character>();
		for (Transition transition : getStartState().getTransitions()) {
			alphabet.addAll(transition.getLabels());
			alphabetWithoutDuplicates.addAll(transition.getLabels());
		}
		// if our start state has epsilon jumps or multiple transitions for any
		// character
		if (alphabet.size() != alphabetWithoutDuplicates.size()
				|| alphabetWithoutDuplicates.contains('ɛ')) {
			return false;
		}

		for (State state : states) {
			ArrayList<Character> stateAlphabet = new ArrayList<Character>();
			for (Transition transition : state.getTransitions()) {
				stateAlphabet.addAll(transition.getLabels());
			}
			Collections.sort(stateAlphabet);
			Collections.sort(alphabet);
			if (!stateAlphabet.equals(alphabet)) {
				return false;
			}
		}
		return true;
	}

	public Automaton convertToDFA() {

		if (this.isDeterministic()) {
			return this;
		}

		HashMap<HashSet<Integer>, State> states = new HashMap<HashSet<Integer>, State>();
		ArrayList<Transition> newTransitions = new ArrayList<Transition>();
		HashSet<Integer> finalStateLabels = new HashSet<Integer>();

		for (State state : this.getStates()) {

			if (state.isFinal()) {
				finalStateLabels.add(state.getLabel());
			}
		}

		//get all labels and put them in a set
		HashSet<Integer> setLabels = new HashSet<Integer>();
		for (State state : getStates()) {
			setLabels.add(state.getLabel());
		}
		// get powerset of all possible states
		HashSet<HashSet<Integer>> possibleStateLabels = getPowerSet(setLabels);

		// create a new state for every possible set
		int stateCounter = 0;
		System.err.println("POOPSIZE OF POWERSET: "+possibleStateLabels.size());
		for (HashSet<Integer> setOfLabels : possibleStateLabels) {
			states.put(setOfLabels, new State(context, stateCounter++));
		}
		System.err.println("POOPDONE CREATING NEW STATES");

		// for every possible state
		for (State state : states.values()) {

			// get the labels (plus the labels after epsilon jumps)
			HashSet<Integer> currentStateLabels = null;
			for (HashSet<Integer> labels : states.keySet()) {
				if (states.get(labels) == state) {
					currentStateLabels = new HashSet<Integer>(labels);
					break;
				}
			}

			for (Integer currentLabel : new HashSet<Integer>(currentStateLabels)) {
				for (State newState : this.getNextStatesAfterEpsilonJump(this
						.getStateByLabel(currentLabel))) {
					currentStateLabels.add(newState.getLabel());
				}
			}

			// get the result states after transitioning on a charater and
			// create transitions
			for (Character letter : this.getAlphabet()) {
				HashSet<State> resultStates = new HashSet<State>();
				HashSet<Integer> resultLabels = new HashSet<Integer>();
				for (Integer currentLabel : currentStateLabels) {
					resultStates.addAll(this.getNextStates(this
							.getStateByLabel(currentLabel), letter));
				}
				for (State resultState : resultStates) {
					resultLabels.add(resultState.getLabel());
				}

				boolean createNewTransition = true;
				for (Transition transitionToMatch : state.getTransitions()) {
					if (transitionToMatch.getEndState() == states
							.get(resultLabels)) {
						transitionToMatch.addLabel(letter);
						createNewTransition = false;
					}
				}
				if (createNewTransition) {
					Transition newTransition = new Transition(state, states
							.get(resultLabels), letter);
					for (Transition transition : states.get(resultLabels)
							.getTransitions()) {
						if (transition.getEndState() == state) {
							transition.setHasOpposite(true);
							newTransition.setHasOpposite(true);
						}
					}
					newTransitions.add(newTransition);
					state.addTransition(newTransition);
				}
			}
		}
		HashMap<State, HashSet<Integer>> labels = reverseHashMap(states);
		for (State state : labels.keySet()) {
			for (Integer label : labels.get(state)) {
				if (this.getStateByLabel(label).isFinal()) {
					state.setFinal(true);
				}

				if (this.getStateByLabel(label).isInitial()) {
					HashSet<Integer> temp = new HashSet<Integer>(labels
							.get(state));
					temp.remove(label);
					if (temp.isEmpty()) {
						state.setInitial(true);
					}
				}
			}
		}

		ArrayList<State> newStates = new ArrayList<State>();
		newStates.addAll(labels.keySet());

		return new Automaton(context, newStates, newTransitions)
				.removeDeadStates();
	}

	public Automaton removeDeadStates() {

		ArrayList<State> visitedStates = new ArrayList<State>();
		ArrayList<State> statesToVisit = new ArrayList<State>();
		ArrayList<Transition> newTransitions = new ArrayList<Transition>();
		statesToVisit.add(this.getStartState());

		while (!statesToVisit.isEmpty()) {
			ArrayList<State> temp = new ArrayList<State>(statesToVisit);
			statesToVisit.clear();
			for (State stateToVisit : temp) {
				visitedStates.add(stateToVisit);
				for (Transition transition : stateToVisit.getTransitions()) {
					newTransitions.add(transition);
					if (!visitedStates.contains(transition.getEndState())
							&& !statesToVisit
									.contains(transition.getEndState())) {
						statesToVisit.add(transition.getEndState());
					}
				}
			}
		}

		return new Automaton(context, visitedStates, newTransitions);
	}

	private HashMap<State, HashSet<Integer>> reverseHashMap(
			HashMap<HashSet<Integer>, State> map) {
		HashMap<State, HashSet<Integer>> rev = new HashMap<State, HashSet<Integer>>();
		for (HashSet<Integer> entry : map.keySet())
			rev.put(map.get(entry), entry);
		return rev;
	}

	private HashSet<HashSet<Integer>> getPowerSet(HashSet<Integer> originalSet) {

		HashSet<HashSet<Integer>> sets = new HashSet<HashSet<Integer>>();

		if (originalSet.isEmpty()) {
			sets.add(new HashSet<Integer>());
			return sets;
		}

		ArrayList<Integer> setLabels = new ArrayList<Integer>(originalSet);
		Integer head = setLabels.get(0);
		HashSet<Integer> rest = new HashSet<Integer>(setLabels.subList(1,
				setLabels.size()));

		for (HashSet<Integer> set : getPowerSet(rest)) {
			HashSet<Integer> newSet = new HashSet<Integer>();
			newSet.add(head);
			newSet.addAll(set);
			sets.add(newSet);
			sets.add(set);
		}
		return sets;
	}

	public State getStateByLabel(int labelToFind) {

		for (State state : getStates()) {

			if (state.getLabel() == labelToFind) {

				return state;
			}
		}
		return null;
	}

	public HashSet<Character> getAlphabet() {

		HashSet<Character> alphabet = new HashSet<Character>();

		for (State state : getStates()) {

			for (Transition transition : state.getTransitions()) {

				alphabet.addAll(transition.getLabels());
			}
		}

		if (alphabet.contains('ɛ')) {
			alphabet.remove('ɛ');
		}
		return alphabet;
	}

	// to string method for printing automaton
	public String toString() {

		String automaton = "";
		// find the initial
		for (State graphic : getStates()) {
			if (graphic.isInitial()) {
				automaton += "initial state: " + graphic.getLabel() + "\n";
				break;
			}
		}
		for (State graphic : getStates()) {
			automaton += "state " + graphic.getLabel();
			if (graphic.isFinal()) {
				automaton += " [accept]:\n";
			} else {
				automaton += " [reject]:\n";
			}
			for (Transition transition : graphic.getTransitions()) {
				automaton += "  ";
				String labels = "";
				for (char transitionCharacter : transition.getLabels()) {
					labels += "-" + transitionCharacter;
				}
				labels = labels.substring(1);
				automaton += labels + " -> "
						+ transition.getEndState().getLabel() + "\n";
			}
		}
		return automaton;
	}

//	public Automaton removeIndestinguishableStates() {
//
//		if (!this.isDeterministic()) {
//			this.convertToDFA();
//		}
//		this.removeDeadStates();
//		
//		ArrayList<StatePair> possibleIndestinguishablePairs = new ArrayList<StatePair>();
//		ArrayList<StatePair> destinguishablePairs = new ArrayList<StatePair>();
//		for (int i = 0; i < getStates().size(); i++) {
//			for (int j = i; j < getStates().size(); j++) {
//				if (i != j) {
//					possibleIndestinguishablePairs.add(new StatePair(
//							getStates().get(i), getStates().get(j)));
//				}
//			}
//		}
//
//		for (StatePair pair : new ArrayList<StatePair>(possibleIndestinguishablePairs)) {
//			if ((pair.getLeft().isFinal() && pair.getRight().isInitial())
//					|| (pair.getLeft().isInitial() && pair.getRight().isFinal())) {
//				possibleIndestinguishablePairs.remove(pair);
//				destinguishablePairs.add(pair);
//			}
//		}
//
//		boolean destinguishablePairsAdded = true;
//		while (destinguishablePairsAdded) {
//			destinguishablePairsAdded = false;
//			for (StatePair pair : possibleIndestinguishablePairs) {
//				for (Character letter : this.getAlphabet()) {
//					StatePair resultPair = new StatePair(
//							(State) this.getNextStates(pair.getLeft(), letter)
//									.toArray()[0], (State) this.getNextStates(
//									pair.getRight(), letter).toArray()[0]);
//					for (StatePair pairToMatch : destinguishablePairs) {
//						if (pairToMatch.equals(resultPair)) {
//							destinguishablePairsAdded = true;
//							destinguishablePairs.add(resultPair);
//							possibleIndestinguishablePairs.remove(resultPair);
//							break;
//						}
//					}
//				}
//			}
//		}
//		for (StatePair pair : possibleIndestinguishablePairs) {
//			Toast.makeText(
//					context,
//					pair.getLeft().getLabel() + ", "
//							+ pair.getRight().getLabel(), Toast.LENGTH_LONG)
//					.show();
//		}
//		//		
//		// we have a list of indestinguishable pairs, lets remove them
//		ArrayList<StatePair> removedStates = new ArrayList<StatePair>();
//		for (StatePair pair : possibleIndestinguishablePairs) {
//			boolean leftRemovedAlready = false;
//			for (StatePair removedPair : removedStates) {
//
//				if (removedPair.getLeft() == pair.getLeft()) {
//					leftRemovedAlready = true;
//					mergeStates(new StatePair(pair.getRight(), removedPair
//							.getRight()));
//				}
//			}
//			if (!leftRemovedAlready) {
//				mergeStates(pair);
//			}
//
//			removedStates.add(pair);
//		}
//		
//		return this;
//	}

//	private void mergeStates(StatePair pair) {
//		// change all of the left states transitions to come from the right
//		// state
//		for (Transition transitionToRemove : pair.getLeft().getTransitions()) {
//			// check to see if it has this transition already
//			boolean hadTransitionAlready = false;
//			for (Transition transitionToCheckIfSame : pair.getRight()
//					.getTransitions()) {
//				// if they are the same
//				if (transitionToCheckIfSame.getEndState() == transitionToRemove
//						.getEndState()) {
//					// just add the labels and remove the bad one
//					transitionToCheckIfSame.addLabels(transitionToRemove
//							.getLabels());
//					this.getTransitions().remove(transitionToRemove);
//					hadTransitionAlready = true;
//					break;
//				}
//			}
//			// if we didnt have that transition already, then just change its
//			// start state
//			if (!hadTransitionAlready) {
//				transitionToRemove.setStartState(pair.getRight());
//			}
//		}
//		// change all transitions going in to the bad state to go in to the good
//		// one
//		for (Transition transitionToChange : new ArrayList<Transition>(this.getTransitions())) {
//			// if this transition goes in to our bad state
//			if (transitionToChange.getEndState() == pair.getLeft()) {
//				// check if the good state already has the transition
//				boolean hadTransitionAlready = false;
//				for (Transition transitionToCheck : new ArrayList<Transition>(this.getTransitions())) {
//					// if this is a similar transition
//					if (transitionToCheck.getEndState() == pair.getRight()
//							&& transitionToCheck.getStartState() == transitionToChange
//									.getStartState()) {
//						transitionToCheck.addLabels(transitionToChange
//								.getLabels());
//						this.getTransitions().remove(transitionToChange);
//						hadTransitionAlready = true;
//					}
//				}
//				// if we didnt have that transition already, then just change
//				// its start state
//				if (!hadTransitionAlready) {
//					transitionToChange.setEndState(pair.getRight());
//				}
//			}
//		}
//		// finally remove the bad state
//		this.getStates().remove(pair.getLeft());
//	}
}